#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <climits>
#include <memory>
#include <algorithm>
#include <numeric>

using namespace std;

// 爬楼梯
// 杨辉三角
// 打家劫舍
// 打家劫舍II
// 打家劫舍III
// 完全平方数 -- 完全背包问题
// 零钱兑换 --- 完全背包
// 单词拆分
// 最长递增子序列
// 乘积最大子数组
// 分割等和数组   ---- 01背包
// 不同路径
// 不同路径II
// 最小路径和
// 最长回文子串
// 最长公共子序列

// 爬楼梯
class Solution
{
public:
    int climbStairs(int n)
    {
        if (n <= 2)
            return n;
        vector<int> dp(n + 1);
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++)
        {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};

// 杨辉三角
class Solution
{
public:
    vector<vector<int>> generate(int numRows)
    {
        vector<vector<int>> dp(numRows);
        for (int i = 0; i < numRows; i++)
        {
            dp[i].resize(i + 1, 0);
            // 第一个和最后一个数为1
            dp[i][0] = dp[i][dp[i].size() - 1] = 1;
        }

        for (int i = 0; i < numRows; i++)
        {
            for (int j = 0; j < dp[i].size(); j++)
            {
                if (dp[i][j] == 0)
                {
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
                }
            }
        }
        return dp;
    }
};

// 打家劫舍
class Solution
{
public:
    int rob(vector<int> &nums)
    {
        int n = nums.size();
        // f[i]:表示偷到i位置,偷nums[i]的最大金额
        // g[i]:表示偷到i位置,不偷nums[i]的最大金额
        vector<int> f(n), g(n);
        f[0] = nums[0];
        for (int i = 1; i < n; i++)
        {
            f[i] = nums[i] + g[i - 1];
            g[i] = max(f[i - 1], g[i - 1]);
        }

        return max(f[n - 1], g[n - 1]);
    }
};

// 打家劫舍II
class Solution
{
public:
    int rob(vector<int> &nums)
    {
        // 这里需要讨论两种情况下的最大值
        // 分为偷第一个和偷最后一个
        int n = nums.size();
        if (n == 1)
            return nums[0];
        return max(rob1(nums, 0, n - 2), rob1(nums, 1, n - 1));
    }

    int rob1(vector<int> &nums, int begin, int end)
    {
        if (end < begin)
            return 0;
        int n = nums.size();
        // f[i]:表示偷到i位置，偷nums[i]时的最大金额
        // g[i]:表示偷到i位置，不偷nums[i]时的最大金额
        vector<int> f(n), g(n);
        f[begin] = nums[begin];
        for (int i = begin + 1; i <= end; i++)
        {
            f[i] = nums[i] + g[i - 1];
            g[i] = max(f[i - 1], g[i - 1]);
        }

        return max(f[end], g[end]);
    }
};

// 打家劫舍III
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution
{
public:
    // 使用一个哈希表来保存每个节点偷或者不偷的最大值
    // 对二叉树进行后续遍历，来依次求其值
    unordered_map<TreeNode *, int> f, g;
    int rob(TreeNode *root)
    {
        if (root == nullptr)
            return 0;
        dfs(root);
        return max(f[root], g[root]);
    }

    void dfs(TreeNode *root)
    {
        if (root == nullptr)
            return;
        dfs(root->left);
        dfs(root->right);
        f[root] = root->val + g[root->left] + g[root->right];
        g[root] = max(f[root->left], g[root->left]) + max(f[root->right], g[root->right]);
    }
};

class Solution
{
public:
    int rob(TreeNode *root)
    {
        auto result = robHelper(root);
        return max(result.first, result.second);
    }

private:
    pair<int, int> robHelper(TreeNode *node)
    {
        if (!node)
            return {0, 0};

        auto left = robHelper(node->left);
        auto right = robHelper(node->right);

        // 不选择当前节点的情况
        int notRobbed = max(left.first, left.second) + max(right.first, right.second);

        // 选择当前节点的情况
        int robbed = node->val + left.first + right.first;

        return {notRobbed, robbed};
    }
};

// 完全平方数 -- 完全背包问题
class Solution
{
public:
    int numSquares(int n)
    {
        //  完全背包：dp[i][j]从前i个物品中挑选,总体积不超过j,所有的选法中,最大的价值
        //  dp[i][j]:从前i个数中，总和等于n，所有的选法中，最少的数量
        //  不选i位置 dp[i][j] = dp[i - 1][j]
        //  选i位置 dp[i][j] = dp[i][j - i * i] + 1
        int m = sqrt(n);
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int j = 1; j <= n; j++)
        {
            dp[0][j] = 0x3f3f3f3f;
        }
        for (int i = 1; i <= m; i++)
        {
            for (int j = 0; j <= n; j++)
            {
                dp[i][j] = dp[i - 1][j];
                if (j >= i * i)
                {
                    dp[i][j] = min(dp[i][j], dp[i][j - i * i] + 1);
                }
            }
        }

        return dp[m][n];
    }
};

class Solution
{
public:
    int numSquares(int n)
    {
        //  完全背包：dp[i][j]从前i个物品中挑选,总体积不超过j,所有的选法中,最大的价值
        //  dp[i][j]:从前i个数中，总和等于n，所有的选法中，最少的数量
        //  不选i位置 dp[i][j] = dp[i - 1][j]
        //  选i位置 dp[i][j] = dp[i][j - i * i] + 1
        int m = sqrt(n);
        vector<int> dp(n + 1, 0x3f3f3f3f);
        dp[0] = 0;
        for (int i = 1; i <= m; i++)
        {
            for (int j = i * i; j <= n; j++)
            {
                dp[j] = min(dp[j], dp[j - i * i] + 1);
            }
        }

        return dp[n];
    }
};

//  完全背包：dp[i][j]从前i个物品中挑选,总体积不超过j,所有的选法中,最大的价值
//  不选i位置 dp[i][j] = dp[i - 1][j]
//  选i位置 dp[i][j] = dp[i][j - nums[i]] + 1
//  01背包
//  不选i位置 dp[i][j] = dp[i - 1][j]
//  选i位置   dp[i][j] = dp[i - 1][j - nums[i]] + 1

// 零钱兑换 --- 完全背包
class Solution
{
public:
    int coinChange(vector<int> &nums, int n)
    {
        // dp[i][j]从前i个硬币中挑选,总和等于amount,所有组合中,最少的硬币个数
        int m = nums.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        // 不选i位置 dp[i][j] = dp[i - 1][n]
        // 选i位置   d[i][j] = dp[i][n - nums[i]]
        for (int j = 1; j <= n; j++)
            dp[0][j] = 0x3f3f3f3f;
        for (int i = 1; i <= m; i++)
        {
            for (int j = 0; j <= n; j++)
            {
                dp[i][j] = dp[i - 1][j];
                if (j >= nums[i - 1])
                {
                    dp[i][j] = min(dp[i][j], dp[i][j - nums[i - 1]] + 1);
                }
            }
        }

        return dp[m][n] >= 0x3f3f3f3f ? -1 : dp[m][n];
    }
};

class Solution
{
public:
    int coinChange(vector<int> &nums, int n)
    {
        // dp[i][j]从前i个硬币中挑选,总和等于amount,所有组合中,最少的硬币个数
        int m = nums.size();
        vector<int> dp(n + 1, 0x3f3f3f3f);
        // 不选i位置 dp[i][j] = dp[i - 1][n]
        // 选i位置   d[i][j] = dp[i][n - nums[i]]
        dp[0] = 0;
        for (int i = 1; i <= m; i++)
        {
            for (int j = nums[i - 1]; j <= n; j++)
            {
                dp[j] = min(dp[j], dp[j - nums[i - 1]] + 1);
            }
        }

        return dp[n] >= 0x3f3f3f3f ? -1 : dp[n];
    }
};

// 单词拆分
class Solution
{
public:
    bool wordBreak(string s, vector<string> &wordDict)
    {
        unordered_set<string> hash;
        for (auto str : wordDict)
        {
            hash.insert(str);
        }
        int n = s.size();
        // dp[i]:表示以i位置为结尾是否可以被拼接
        // j为最后一个单词的起始位置 0 <= j <= i
        // dp[i] = dp[j - 1] && (j ~ i)在字典中
        // j - 1会越界,添加一个虚拟节点
        vector<bool> dp(n + 1);
        dp[0] = true;
        s = ' ' + s;
        for (int i = 1; i <= n; i++)
        {
            // 注意这里是j >= 1
            // j为最后一个单词的起始位置 0 <= j <= i
            for (int j = i; j >= 1; j--)
            {
                if (dp[j - 1] && hash.count(s.substr(j, i - j + 1)))
                {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[n];
    }
};

// 最长递增子序列
class Solution
{
public:
    int lengthOfLIS(vector<int> &nums)
    {
        int n = nums.size();
        // dp[i]:表示以i位置为结尾的最长递增子序列的长度
        // dp[i] = dp[i - j] + 1 0 <= j < j
        // [10,9,2,5,3,7,101,18]如果不把所有的初始化为1
        // 那么9的时候,dp[1] = 0,所以要把所有的都初始化为1,不是单单初始化dp[0]
        vector<int> dp(n, 1);
        int ans = 1;
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (nums[i] > nums[j])
                {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
                ans = max(ans, dp[i]);
            }
        }
        return ans;
    }
};

// 乘积最大子数组
class Solution
{
public:
    int maxProduct(vector<int> &nums)
    {
        // f[i]:表示以i位置为结尾的所有子数组乘积的最小值
        // g[i]:表示以i位置为结尾的所有子数组乘积的最大值
        // 我们需要注意的是,nums[i]位置的值的正负号，如果为正就乘以前一个的最大值
        // 如果为负，乘以上一个的最小值，这样才能得到最大值
        // 所有这里维护一个最大值和一个最小值的dp
        // f[i] = max(nums[i],nums[i]*f[i-1],nums[i]*g[i-1]);
        int n = nums.size();
        vector<int> f(n), g(n);
        int ans = nums[0];
        f[0] = g[0] = nums[0];
        for (int i = 1; i < n; i++)
        {
            int x = nums[i] * f[i - 1], y = nums[i] * g[i - 1];
            f[i] = max(nums[i], max(x, y));
            g[i] = min(nums[i], min(x, y));
            ans = max(f[i], ans);
        }

        return ans;
    }
};

// 分割等和数组   ---- 01背包
class Solution
{
public:
    bool canPartition(vector<int> &nums)
    {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % 2 == 1)
            return false;
        // dp[i][j]:从前i个数组中是否能得到和为j
        // 不选i. dp[i][j] = dp[i - 1][j]
        // 选i.  dp[i][j] = dp[i - 1][j - nums[i]]
        int aim = sum / 2;
        int n = nums.size();
        vector<vector<bool>> dp(n + 1, vector<bool>(aim + 1));
        // j == 0 表示和为0,不选即可
        for (int i = 0; i <= n; i++)
            dp[i][0] = true;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= aim; j++)
            {
                dp[i][j] = dp[i - 1][j];
                if (j >= nums[i - 1])
                {
                    dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
                }
            }
        }

        return dp[n][aim];
    }
};

// 不同路径
class Solution
{
public:
    int uniquePaths(int m, int n)
    {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));

        dp[0][1] = 1;
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

        return dp[m][n];
    }
};

// 不同路径II
class Solution
{
public:
    int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid)
    {
        // 我们将有障碍物位置的dp位置的值设置0即可
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        dp[0][1] = 1;
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                // 注意映射关系,obstacleGrid[i-1][j-1]映射的是dp[i][j]位置
                // obstacleGrid[i-1][j-1]位置有障碍物,那么dp[i][j]=0
                if (obstacleGrid[i - 1][j - 1] == 0)
                {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }

        return dp[m][n];
    }
};

// 最小路径和
class Solution
{
public:
    int minPathSum(vector<vector<int>> &grid)
    {
        // dp[i][j]:表示到i,j位置最小路径和
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
        dp[0][1] = dp[1][0] = 0;
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                dp[i][j] = grid[i - 1][j - 1] + min(dp[i - 1][j], dp[i][j - 1]);
            }
        }

        return dp[m][n];
    }
};

// 最长回文子串
class Solution
{
public:
    string longestPalindrome(string s)
    {
        // dp[i][j]表示以i为起始位置j为结束位置的子串是否为回文子串
        // s[i] == s[j] i + 1 < j dp[i][j] = dp[i + 1][j - 1]
        // i == j || i + 1 == j  dp[i][j] = true
        // s[i] != s[j] dp[i][j] = false
        int n = s.size();
        int begin = 0, len = 1;
        vector<vector<bool>> dp(n, vector<bool>(n));
        dp[0][0] = true;
        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = i; j < n; j++)
            {
                if (s[i] == s[j])
                {
                    if (i == j || i + 1 == j)
                        dp[i][j] = true;
                    else
                        dp[i][j] = dp[i + 1][j - 1];
                }
                else
                    dp[i][j] = false;

                // 长度大于最大长度且为true
                // 更新最大长度和起始位置
                if (dp[i][j] && j - i + 1 > len)
                {
                    begin = i;
                    len = j - i + 1;
                }
            }
        }

        return s.substr(begin, len);
    }
};

// 最长公共子序列
class Solution
{
public:
    int longestCommonSubsequence(string text1, string text2)
    {
        // dp[i][j]表示s1[0,i]区间以及s2[0,j]区间的子序列的公共子序列的最长长度
        int m = text1.size(), n = text2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        // i == 0 s1为空串
        // j == 0 s2为空串
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (text1[i - 1] == text2[j - 1])
                {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }

        return dp[m][n];
    }
};